#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
#include<string>
using namespace std;

//int main()
//{
//    int a;
//    while (cin >> a)
//    {
//        int x = 0;
//        int y = 1;
//        while (y < a)
//        {
//            int next = x + y;
//            x = y;
//            y = next;
//        }
//        int ret = (y - a) < (a - x) ? (y - a) : (a - x);
//        cout << ret << endl;
//    }
//    return 0;
//}

//int main() {
//    int a;
//
//    while (cin >> a)
//    {
//        vector<vector<int>> yang;
//        yang.reserve(a);
//        for (int i = 1; i <= a; ++i)
//        {
//            vector<int> tmp(i, 1);
//            for (int j = 1; j < i - 1; ++j)
//            {
//                tmp[j] = yang[i - 2][j] + yang[i - 2][j - 1];
//            }
//            yang.push_back(tmp);
//        }
//        for (int i = 0; i < a; ++i)
//        {
//            for (int j = 0; j <= i; ++j)
//            {
//                printf("%5d", yang[i][j]);
//            }
//            cout << endl;
//        }
//    }
//    return 0;
//}


class Solution {
public:
    bool _exist(vector<string>& board, string word, int x, int y)
    {
        string tmp(++word.begin(), word.end());
        if (tmp == "")
            return true;
        if (x + 1 < board.size() && board[x + 1][y] == tmp[0])
        {
            if (_exist(board, tmp, x + 1, y))
                return true;
        }
        if (x - 1 >= 0 && board[x - 1][y] == tmp[0])
        {
            if (_exist(board, tmp, x - 1, y))
                return true;
        }
        if (y + 1 < board[x].size() && board[x][y + 1] == tmp[0])
        {
            if (_exist(board, tmp, x, y + 1))
                return true;
        }
        if (y - 1 >= 0 && board[x][y - 1] == tmp[0])
        {
            if (_exist(board, tmp, x, y - 1))
                return true;
        }
        return false;
    }

    bool exist(vector<string>& board, string word)
    {
        size_t s1 = board.size();
        for (int i = 0; i < s1; ++i)
        {
            size_t s2 = board[i].size();
            for (int j = 0; j < s2; ++j)
            {
                if (board[i][j] == word[0])
                {                  
                    if (_exist(board, word, i, j))
                        return true;
                }
            }
        }
        return false;
    }
};
int main()
{
    vector<string> v = { "XYZE", "SFZS", "XDEE" };
    cout << Solution().exist(v, "XYZZED") << endl;
    return 0;
}